package com.leetcode.dfs;

public class Leetcode394 {
    String res = "";
    public String decodeString(String s) {
        dfs(s, 0, s.length(), "");
        return res;
    }

    private void dfs(String s, int start, int end,  String path) {
        if (start == end) {
            res += path;
            return;
        }

        for (int i = start; i <= end; i++) {
            if (isDigit(s.charAt(i))) {
                String nums = getNums(s, start);
                i += nums.length();
                for (int j = 0; j < Integer.parseInt(nums); j++) {
                    dfs(s, start, getEndIndex(s, start), path);
                }
            } else {
                path += s.charAt(i);
            }
        }
    }

    private boolean isDigit(char c) {
        return c >= '0' && c <= '9';
    }

    private String getNums(String s, int index) {
        String num = "";
        while (s.charAt(index) != '[') {
            num += s.charAt(index++);
        }
        return num;
    }

    private int getEndIndex(String s, int start) {
        while (s.charAt(start) != ']') {
            start++;
        }
        return start;
    }

    public static void main(String[] args) {
        String s = "3[a]2[b]";
        System.out.println(new Leetcode394().decodeString(s));
    }
}
